The subject invention relates to a method whereby a message originator can generate a message including a verifiable assertion that a variable is within predetermined limits. More particularly it relates to cryptographic indicia, and still more particularly, to cryptographic indicia that require a change of cryptographic keys used therefor based on a non-time parameter of the cryptographic indicia.
There are many cases where a message originator can originate only a limited number or type of messages. A party may have the right to issue a limited number of tickets, identification documents, etc., either as printed documents or as digital messages. Similarly an agent may have authority to draw against a principle""s account for amounts up to a predetermined limit, or have authority to act for a certain time period. Each such act by such a party is a message implicitly or explicitly asserting that a variable (e.g. a serial number, or amount, or date) is within predetermined limits. Clearly it would be highly desirable if another party receiving such a message could verify that those limits were not exceeded.
A particular example where such capability would be useful relates to cryptographic postal indicia. The United States Postal Service (USPS) is currently advocating the implementation of a new Information-Based Indicia Program (IBIP) in connection with the printing of postage indicia by postage metering systems. Under this new program, each postage indicium that is printed will include cryptographically secured information in a barcode format together with human readable information such as the postage amount and the date of submission to the post office. The cryptographically secured information is generated using public key cryptography and allows a verification authority (hereinafter sometimes xe2x80x9cverifierxe2x80x9d), such as the post office, to verify the authenticity of the printed postage indicium based on the information printed in the indicium and the printed destination address. Moreover, it has also been proposed to use secret key cryptography as an alternative to the public key system described above. In the secret key system verifiable cryptographically secured information is also included as part of the indicium.
Regardless of whether a public or secret key system is utilized, both systems use a key that is securely and secretly stored within the postage meter. This stored key is referred to as a private key in a public key system and a secret key in a secret key system. In either case, the stored key is used to cryptographically secure certain information contained within the printed postage indicium. However, since the security of either system is dependent upon maintaining the secrecy of the stored key, it is imperative that such stored key not be compromised.
One of the factors that increases the vulnerability of the stored key to attacks such as cryptoanalysis, differential fault analysis, and differential power analysis is the amount of its use. That is, the more the stored key is used to cryptographically secure data the more vulnerable it is to these attacks. In order to partially solve this problem, it has been suggested to require the postage meter to obtain a new secret key after a predetermined period of time has expired. The problem with this method is that it does not necessarily reflect the actual usage of the stored key in generating cryptographically secured indicia images. Thus, if a specific postage meter has extremely high usage, waiting for the predetermined period of time to expire before requiring the changing of the stored key may not be a satisfactory security solution.
One solution to this problem would be to incorporate a variable, e.g. piece count, which is a measure of meter usage into the postal indicia along with information which would allow a verifier to verify that the variable was within predetermined limits. Since the piece count is typically a part of the signed data in a postal indicium its accuracy is assured and verification that it lies within predetermined limits would provide an accurate indication of the need to change the meter key.
In other applications the variable forms an inherently required part of the message and is self verifying, e.g. the amount of a check, or can be directly determined by the verifier, e.g. a quantity of goods ordered from a supplier. Thus verifiable information that the amount was within the authority of an agent would prevent agents from writing checks or ordering quantities which exceeded their authority.
Accordingly, it is an object of the subject invention to provide a method and system wherein a message originator is enabled and authorized by a third party to generate a verifiable message asserting that a variable is within predetermined limits only if the variable is within those predetermined limits.
The above object is achieved and the disadvantages of the prior are overcome in accordance with the subject invention by means of a system and method for generation of a message from which it can be verified that a variable is within predetermined upper and lower limits. In accordance with the invention a trapdoor function R is provided to a message originator and to a message verifier, and a third party maintains a corresponding inverse function Rxe2x88x921 in secrecy an integer K equal to the difference between said upper limit and said lower limit is determined; and a second message including Rxe2x88x92k(T) is provided from said third party to said message originator, wherein T is a plain text coded as an integer and Rxe2x88x92k(T) represents K iterations of said inverse function Rxe2x88x921 with said coded text T. The message originator generates a third message Sx=Rx(Rxe2x88x92k(T)); wherein Rx(Rxe2x88x92k(T)) represents x iterations of said function R with Rxe2x88x92k(T); and wherein x is an integer equal to the absolute value of the difference between a current value of said variable and one of said limits; and incorporates at least said third message Sx into said first message to assert that said current value of said variable is within said limits A verifier receiving said first message recovers Sx and determines said current value of said variable and said other limit; and confirms that Ry(Sm)=T; wherein Ry(Sm) represents y iterations of said function R with said third message Sm and wherein y is an integer equal to the absolute value of the difference between said current value of said variable and said other limit.
In accordance with one aspect of the subject invention the first message is a postal indicium.
In accordance with another aspect of the subject invention the postal indicium is encrypted by a postage metering system using an encryption key and said second message is transmitted to said system when said key is changed.
In accordance with another aspect of the subject invention the plain text T includes an identification of said postage metering system.
In accordance with another aspect of the subject invention the plain text T further includes said other limit.
In accordance with another aspect of the subject invention the current value of said variable is provided to said verifier by incorporation in said first message.
In accordance with another aspect of the subject invention the current value of said variable is inherent in the meaning of said first message.
In accordance with another aspect of the subject invention the current value of said variable is determined directly by said verifier.
In accordance with another aspect of the subject invention the third message Sx comprises said first message.
In accordance with another aspect of the subject invention the one limit is said lower limit.
In accordance with another aspect of the subject invention the one limit is said upper limit.